#include "base.h"

class Solution
{
public:
    vector<string> res;
    void recur(string &str, int lcnt, int rcnt)
    {
        if (lcnt == rcnt && lcnt + rcnt == str.size())
        {
            res.push_back(str);
            return;
        }
        if (lcnt > str.size() / 2)
        {
            return;
        }
        {
            str[lcnt + rcnt] = '(';
            recur(str, lcnt + 1, rcnt); //向左
        }
        if (rcnt < lcnt)
        {
            str[lcnt + rcnt] = ')';
            recur(str, lcnt, rcnt + 1);
        }
    }
    vector<string> generateParenthesis(int n)
    {
        res.clear();
        string buf;
        buf.resize(n * 2);
        recur(buf, 0, 0);
        return res;
    }
};

int main()
{
    auto a = Solution().generateParenthesis(3);

    return 0;
}